package com.yincb.sort;

import java.util.Arrays;

public class InsertSort {

    /**
     * 插入排序         { 9, 8, 7, 0, 1, 3, 2 }
     * 第1次的排序结果为：[8, 9, 7, 0, 1, 3, 2]
     * 第2次的排序结果为：[7, 8, 9, 0, 1, 3, 2]
     * 第3次的排序结果为：[0, 7, 8, 9, 1, 3, 2]
     * 第4次的排序结果为：[0, 1, 7, 8, 9, 3, 2]
     * 第5次的排序结果为：[0, 1, 3, 7, 8, 9, 2]
     * 第6次的排序结果为：[0, 1, 2, 3, 7, 8, 9]
     * <p>
     * 1.将数组分成已排序段和未排序段。初始化时已排序端只有一个元素
     * 2.到未排序段取元素插入到已排序段，并保证插入后仍然有序
     * 3.重复执行上述操作，直到未排序段元素全部加完。
     * 时间复杂度 O(n^2)
     */

    public static void main(String[] args) {

        int a[] = {9, 8, 7, 0, 1, 3, 2};
        int n = a.length; // 7

        for (int i = 1; i < n; i++) {
            int tem = a[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (a[j] > tem) {
                    a[j + 1] = a[j];
                } else {
                    break; // 插入排序 其实就是对这个break排序，插入排序对已经排好的数列排数很快，时间复杂度O(n)
                }
            }
            a[j + 1] = tem;
            System.out.println("第" + i + "次的排序结果为：" + Arrays.toString(a));
        }

    }


}
